package leetcode_day._2021._202106._2130;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/30 16:01
 * 序列化二叉树
 * 算法：二叉树 层序遍历
 */
public class _30_剑指offer37 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

//    class Codec {
//        private TreeNode root;
//        // Encodes a tree to a single string.
//        public String serialize(TreeNode root) {
//            this.root = root;
//            return null;
//        }
//
//        // Decodes your encoded data to tree.
//        public TreeNode deserialize(String data) {
//            return root;
//        }
//    }

    class Codec {
        private TreeNode emptyNode = new TreeNode(-2000);
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (null == root) return "";
            StringBuilder ans = new StringBuilder();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                ans.append(cur.val).append("_");
                // 只要是不为空的节点，都可以加左右节点到队列中
                if (!cur.equals(emptyNode)) {
                    queue.offer(cur.left == null ? emptyNode : cur.left);
                    queue.offer(cur.right == null ? emptyNode : cur.right);
                }
            }
            return ans.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if ("".equals(data)) return null;
            String[] s = data.split("_");
            TreeNode root = new TreeNode(Integer.parseInt(s[0]));
            Queue<TreeNode> queue = new LinkedList<>();
            // 序列化后，得到的是一颗满二叉树，不算根节点后，数量是 2 的 n 次倍
            for (int i = 1; i < s.length - 1; i += 2) {
                TreeNode cur = queue.poll();
                int a = Integer.parseInt(s[i]), b = Integer.parseInt(s[i + 1]);
                if (a != -2000) {
                    cur.left = new TreeNode(a);
                    queue.offer(cur.left);
                }
                if (b != -2000) {
                    cur.right = new TreeNode(b);
                    queue.offer(cur.right);
                }
            }
            return root;
        }
    }

}
